//给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。 
//
// 连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 
//val 的绝对值。 
//
// 请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
//输出：20
//解释：
//
//我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
//注意到任意两个点之间只有唯一一条路径互相到达。
// 
//
// 示例 2： 
//
// 
//输入：points = [[3,12],[-2,5],[-4,1]]
//输出：18
// 
//
// 示例 3： 
//
// 
//输入：points = [[0,0],[1,1],[1,0],[-1,1]]
//输出：4
// 
//
// 示例 4： 
//
// 
//输入：points = [[-1000000,-1000000],[1000000,1000000]]
//输出：4000000
// 
//
// 示例 5： 
//
// 
//输入：points = [[0,0]]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= points.length <= 1000 
// -106 <= xi, yi <= 106 
// 所有点 (xi, yi) 两两不同。 
// 
// Related Topics 并查集 
// 👍 69 👎 0
#include <iostream>
#include <vector>

using namespace std;

class Djset {
public:
    vector<int> parent; // 记录节点的根
    vector<int> rank;   // 记录根节点的深度（用于优化）
    vector<int> size;   // 记录每个连通分量的节点个数
    vector<int> len;    // 记录每个连通分量里的所有边长度
    int num;            // 记录节点个数
    Djset(int n): parent(n), rank(n), len(n, 0), size(n, 1), num(n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int Find_set(int x) {
        // 压缩方式：直接指向根节点
        if (x != parent[x]) {
            parent[x] = Find_set(parent[x]);
        }
        return parent[x];
    }

    int Union_set(int x, int y, int length) {
        int rootx = Find_set(x);
        int rooty = Find_set(y);
        if (rootx != rooty) {
            if (rank[rootx] < rank[rooty]) {
                swap(rootx, rooty);
            }
            parent[rooty] = rootx;
            if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
            // rooty的父节点设置为rootx,同时将rooty的节点数和边长度累加到rootx,
            size[rootx] += size[rooty];
            len[rootx] += len[rooty] + length;
            // 如果某个连通分量的节点数 包含了所有节点，直接返回边长度
            if (size[rootx] == num) return len[rootx];
        }
        return -1;
    }
};
struct VP {
    int start; // 顶点1
    int end;   // 顶点2
    int len;   // 长度
};
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int res = 0;

        Djset ds(points.size());

        vector<VP> edges;

        for (int i = 0; i < points.size(); ++i) {
            for (int j = i+1; j < points.size(); ++j) {
                VP vp = {i,j,abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])};
                edges.emplace_back(vp);
            }
        }

        sort(edges.begin(),edges.end(),[](const auto& a, const auto& b) {
            return a.len < b.len;
        });

        for (auto& edge : edges){
            res = ds.Union_set(edge.start,edge.end,edge.len);
            if (res != -1){
                return res;
            }
        }
        return 0;
    }
};
//leetcode submit region end(Prohibit modification and deletion)
